﻿#pragma once
#include <iostream>
#include <exception>
#include <vector>
#include <unordered_map>
#include <thread>
#include <mutex>
#include <algorithm>
#include <ctime>
#include <cassert>

#ifdef _WIN32
#include <Windows.h>
#else
//包含linux下brk mmap等头文件
#endif
using std::cout;
using std::endl;
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}
#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#elif
	//Linux等平台
#endif
static const size_t MAX_BYTES = 256 * 1024;//线程最大缓存256KB
static const size_t NFREE_LIST = 208;//哈希桶的个数
static const size_t NPAGES = 129;//页缓存最大哈希桶中的页大小
static const size_t PAGE_SHIFT = 13;//页的移动值
/**
  * @brief  获取对象的/头4/8个字节
  * @param  obj：对象的地址
  * @retval 返回对象的/头4/8个字节
  */
static void*& NextObj(void* obj)
{
	return *(void**)obj;
}
//管理切出来的内存对象的类
class FreeList
{
public:
	void Push(void* obj)
	{
		//头插
		assert(obj);
		NextObj(obj) = _freeList;
		_freeList = obj;
		++_size;
	}
	void* Pop()
	{
		//头删
		assert(_freeList); 
		void* obj = _freeList;
		_freeList = NextObj(_freeList);
		--_size;
		return obj;
	}
	bool Empty()
	{
		return nullptr == _freeList;
	}
	size_t& MaxSize()//偷家函数
	{
		return _maxSize;
	}
	/**
	  * @brief  线程缓存从中央缓存获得内存对象，插入进线程缓存对应的的哈希桶中
	  * @param  start：申请到的对象起始地址的下一个地址
	  * @param  end：申请到的对象结束地址
	  * @param  n：插入的对象的个数，以备回收
	  * @retval 无返回值
	  */
	void PushRange(void* start, void* end,size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;
		//测试验证插入个数是否有n个
		//测试验证+条件断点
		//void* cur = start;
		//int i = 0;
		//while (cur)
		//{
		//	cur = NextObj(cur);
		//	++i;
		//}
		//if (n != i)
		//{
		//	int x = 0;//断点
		//}
		_size += n;
	}
	/**
	  * @brief  从线程缓存中拿出n个内存对象，以备交给中央缓存回收
	  * @param  start：归还的对象起始地址
	  * @param  end：归还的对象结束地址
	  * @param  n：归还的对象的个数，以备回收
	  * @retval 无返回值
	  */
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n >= _size);
		start = _freeList;
		end = start;
		for (size_t i = 0; i < n - 1; ++i)
		{
			end = NextObj(end);
		}
		_freeList= NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}
	size_t Size()
	{
		return _size;
	}
private:
	void* _freeList = nullptr; 
	size_t _maxSize = 1;
	size_t _size=0;//记录当前自由链表挂载内存块的个数，以备回收
};

//计算对象大小的对齐映射规则
class SizeClass//使用静态成员函数，无需对象也能调用
{
public:
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128] 8byte对齐       freelist[0,16)
	// [128+1,1024] 16byte对齐   freelist[16,72)
	// [1024+1,8*1024] 128byte对齐   freelist[72,128)
	// [8*1024+1,64*1024] 1024byte对齐     freelist[128,184)
	// [64*1024+1,256*1024] 8*1024byte对齐   freelist[184,208)
	/**
	  * @brief  RoundUp的子函数，用于计算线程申请的内存对象向上对齐后的大小
	  * @param  bytes：需要申请的字节
	  * @param  alignNum：对齐数
	  * @retval 返回线程申请的内存对象向上对齐后的大小
	  */
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		return (bytes + alignNum - 1) & ~(alignNum - 1);
	}
	/*size_t _RoundUp(size_t size, size_t alignNum)
	{
		size_t alignSize = 0;
		if (size % alignNum != 0)
		{
			alignSize = ((size / alignNum) + 1) * alignNum;
		}
		else
			alignSize = size;
		return alignSize;
	}*/
	/**
	  * @brief  用于计算线程申请的内存对象向上对齐后的大小
	  * @param  bytes：需要申请的字节
	  * @param  alignNum：对齐数
	  * @retval 返回线程申请的内存对象向上对齐后的大小
	  */
	static inline size_t RoundUp(size_t bytes)
	{
		if (bytes <= 128)
		{
			return _RoundUp(bytes, 128);
		}
		else if (bytes <= 1024)
		{
			return _RoundUp(bytes, 1024);
		}
		else if (bytes <= 8 * 1024)
		{
			return _RoundUp(bytes, 8*1024);
		}
		else if (bytes <= 64 * 1024)
		{
			return _RoundUp(bytes, 64*1024);
		}
		else if (bytes <= 256 * 1024)
		{
			return _RoundUp(bytes, 256*1024);
		}
		else//大于256KB的情况
		{
			return _RoundUp(bytes, 1 << PAGE_SHIFT);//8KB对齐
		}
	}
	
	/**
	  * @brief  Index的子函数，用于计算线程申请的内存对象向上对齐后位于哪一个桶
	  *			同样适用于线程缓存向中心缓存归还内存对象时，计算归还对象位于哪一个桶
	  * @param  bytes：需要申请的字节-上一个区间的大小
	  * @param  alignNum：对齐数的移位值
	  * @retval 返回线程申请的内存对象向上对齐后位于哪一个桶
	  */
	static inline size_t _Index(size_t bytes,size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}
	//static inline size_t _Index(size_t bytes,size_t alignNum)//bytes：需要申请的字节；alignNum：对齐数
	//{
	//	if (bytes % alignNum == 0)
	//	{
	//		return bytes / alignNum - 1;
	//	}
	//	else
	//		return bytes / alignNum;
	//}
	/**
	  * @brief  用于计算线程申请的内存对象向上对齐后位于哪一个桶
	  *			同样适用于线程缓存向中心缓存归还内存对象时，计算归还对象位于哪一个桶
	  * @param  bytes：需要申请的字节
	  * @param  alignNum：对齐数的移位值
	  * @retval 返回线程申请的内存对象向上对齐后位于哪一个桶
	  */
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) {
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024) {
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024) {
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1]
				+ group_array[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] +
				group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
		}
		return -1;
	}
	/**
	  * @brief  慢调节算法的一部分，控制线程缓存单次从中央缓存获取多少个对象
	  * @param  size：单个对象的大小
	  * @retval 返回线程缓存单次从中央缓存获取多少个对象
	  */
	static size_t NumMoveSize(size_t size)//size:
	{
		assert(size > 0);
		// [2, 512]，一次批量分配多少个对象的(慢启动)上限值
		int num = MAX_BYTES / size;//256KB/size
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;
		return num;
	}
	/**
	  * @brief  central cache向page cache申请内存，page cache分配内存算法
	  * @param  size：单个对象的大小
	  * @retval 返回申请的页数
	  */
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);//返回线程缓存单次从中央缓存获取多少个对象
		size_t npage = num * size;
		npage >>= PAGE_SHIFT;//右移13位,相当于除等8KB
		if (npage == 0)
			npage = 1;
		return npage;
	}
private:
};
//管理多个连续页的大块内存(带头双向循环链表的节点——页节点)
struct Span//Span不仅central cache会用到，page cache也会用到，所以放到了Common.h
{
	PAGE_ID _pageId = 0;//页号，类似地址。32位程序2^32，每一页8K，即2^32/2^13=2^19页；64位会有2^51页。
	size_t _n = 0;//页数
	//带头双向循环链表
	Span* _next = nullptr;//记录上一个页的地址
	Span* _prev = nullptr;//记录下一个页的地址
	size_t _useCount = 0;//已经“借给”Thread Cache的小块内存的计数
	void* _freeList = nullptr;//未被分配的切好的小块内存自由单链表，挂载在页下
	bool _isUse = false;//当前Span是否在被使用，未使用则处于页缓存，可用于合并
	size_t _objSize = 0;//切好的小对象的大小
};
//页的带头双向循环链表(带桶锁)
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		assert(_head);
		_head->_prev = _head;
		_head->_next = _head;
	}
	void Insert(Span* pos, Span* newSpan)//在pos位置之前插入
	{
		assert(pos);
		assert(newSpan);
		Span* prevSpan = pos->_prev;
		newSpan->_prev = prevSpan;
		prevSpan->_next = newSpan;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}
	void PushFront(Span* newSpan)
	{
		Insert(Begin(), newSpan);
	}
	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}
	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);
		/*if (pos == _head)//1、条件断点2、查看栈帧
		{
			int x = 0;
		}*/
		pos->_prev->_next = pos->_next;
		pos->_next->_prev = pos->_prev;
		//这里pos不用delete，因为要还给下一层page cache
	}
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}
	bool Empty()
	{
		return _head->_next == _head;
	}
private:
	Span* _head;//哨兵位
public:
	std::mutex _mtx;//桶锁
};